package 中等.贪心思想;

import java.util.Arrays;

/**
 * 你的初始 能量 为 power，初始 分数 为 0，只有一包令牌 tokens 。其中 tokens[i] 是第 i 个令牌的值（下标从 0 开始）。
 * 令牌可能的两种使用方法如下：
 * 如果你至少有 token[i] 点 能量 ，可以将令牌 i 置为正面朝上，失去 token[i] 点 能量 ，并得到 1 分 。
 * 如果我们至少有 1 分 ，可以将令牌 i 置为反面朝上，获得 token[i] 点 能量 ，并失去 1 分 。
 * 每个令牌 最多 只能使用一次，使用 顺序不限 ，不需 使用所有令牌。
 * 在使用任意数量的令牌后，返回我们可以得到的最大 分数 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/bag-of-tokens
 */
public class 令牌放置_948 {

    public static void main(String[] args) {

        System.out.println(bagOfTokensScore(new int[]{26}, 51));

    }

    /**
     * 贪心+排序+双指针
     * 1，使用能量将当前令牌中较小的令牌尽可能多的正面朝上
     * 2，如果当前分数 >0 ，那么失去 1 分选择最大的令牌获取能量
     * 3，持续此过程，取过程中总分数的最大值
     */
    public static int bagOfTokensScore(int[] tokens, int power) {
        int maxScore = 0, curScore = 0;
        Arrays.sort(tokens);
        int left = 0, right = tokens.length - 1;

        while (left <= right && (curScore > 0 || power >= tokens[left])) {

            while (left <= right && tokens[left] <= power) {
                power -= tokens[left];
                left++;
                curScore++;
            }
            maxScore = Math.max(maxScore, curScore);

            if (curScore > 0) {
                power += tokens[right];
                right--;
                curScore--;
            }
        }
        return maxScore;
    }

}
